package a2_linkedlist.singlelinkedlist;
/**
 * 火车类，是由多个车厢连接起来的
 */
public class SingleLinkedList {
    //当前火车中车厢节点的个数(实际就是元素的个数)
    private int size;
    //当前火车的头车厢地址
    private Node head;

    /****  添加  *********************/
    //头插法
    public void addFirst(int val){
        //新建一个车厢节点
        Node node = new Node(val);
        //先判断当前火车是否为空
        if(head == null){
            head = node;
        }else{
            //火车头有节点，要把当前新车厢挂载到火车头部
            //先把原本的头部车厢指向新车厢的下一节
            node.next = head;
            //再将这个新增的车厢node指向头部head
            head = node;
        }
        size++;
    }
    //索引插入
    public void addIndex(int index,int val){
        //先判断是否索引越界
        if(index<0||index>size){
            System.err.println("add index illegal!");
            return;
        }
        //index==0，说明是头插
        if(index == 0){
            addFirst(val);
            return;
        }
        //创建一个新的车厢
        Node node = new Node(val);
        //建一个prev，寻找插入位置的前驱,从头节点开始向后走index-1步
        Node prev = head;
        for(int i=0;i<index-1;i++){
            prev = prev.next;
        }
        //node的下一节指向前驱temp的下一节
        node.next = prev.next;
        //前驱的下一节指向node
        prev.next = node;
        size++;
    }
    //尾插
    public void addLast(int val){
        addIndex(size,val);
    }

    /****  查找  *********************/
    //返回索引处value的值
    public int get(int index){
        if(rangeCheck(index)){
            //从头节点开始，走到index的位置
            Node node = head;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            return node.val;
        }else{
            System.err.println("get index illegal!");
            return -1;
        }
    }
    //判断链表中是否有value这个数据、
    public boolean contains(int val){
        for(Node temp=head;temp!=null;temp=temp.next){
            if(temp.val == val)
                return true;
        }
        return false;
    }

    /****  修改  *********************/
    //将单链表中索引为index的元素修改，并返回修改前的值
    public int set(int index,int val){
        if(rangeCheck(index)){
            Node node = head;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            int old = node.val;
            node.val = val;
            return old;
        }else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

    /****  删除  *********************/
    //删除索引处的数据
    public void removeIndex(int index){
        if(rangeCheck(index)){
            if(index == 0){
                Node temp = head;
                head = head.next;
                temp.next = null;
                size--;
            }else{
                //找到待删除节点的前驱
                Node prev = head;
                for(int i=0;i<index-1;i++){
                    prev = prev.next;
                }
                //cur表示待删除节点
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
            }
        }else{
            System.err.println("remove index illegal!");
        }
    }
    //删除单链表中的第一个value值
    public void removeOnceValue(int val){
        //遍历链表，找到value的节点的前驱
        //头节点没有前驱，要特殊处理
        if(head!=null && head.val == val){
            removeIndex(0);
            return;
        }
        //找待删节点的前驱，该前驱的下一节点就是value
        Node prev = head;
        while(prev.next != null){
            if(prev.next.val == val){
                //cur就是待删节点
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
                return;
            }
            //prev不是待删节点的前驱，让prev继续向后走
            prev = prev.next;
        }
    }
    //删除单链表中的全部value值
    public void removeAllValue(int val){
        //判断头节点是否为待删除节点
        while(head!=null && head.val==val){
            head = head.next;
            size--;
        }
        if(head == null){
            //说明链表中全是待删节点，此时链表被删空
            return;
        }else{
            //此时head一定不是待删节点,再看链表中的其它节点
            Node prev = head;
            while(prev.next != null){
                if(prev.next.val == val){
                    //cur就是待删节点
                    Node cur = prev.next;
                    prev.next = cur.next;
                    cur.next = null;
                    size--;
                }else{
                    //只有确保prev的下一个不是待删节点，才让prev继续向后走一步
                    prev = prev.next;
                }
            }
        }
    }
    //清空链表
    public void clear(){
        head = null;
        size = 0;
    }

    //打印
    public String toString(){
        String str = "";
        //遍历这个火车类，从头部(head)走到尾部
        //暂时存储头节点地址，避免遍历结束影响head的值
        Node node = head;
        while(node != null){
            str += node.val;
            str += " -> ";
            //当前地址指向下一节车厢的地址
            node = node.next;
        }
        str += "NULL";
        return str;
    }
    //判断 查、改、删操作时，索引是否越界
    private boolean rangeCheck(int index){
        if(index<0||index>=size)
            return false;
        else
            return true;
    }
    public int size(){
        return this.size;
    }
}
